package one.collectionAndMap;

import java.util.*;

/**
 * 字母异位词分组
 * 时间复杂度：O(nlogn+n)
 * 思路：HashMap（可用于分组）
 * ["eat", "tea", "tan", "ate", "nat", "bat"](value)===》["aet", "aet", "ant", "aet", "ant", "abt"](key)
 * 从排序后的字符串（aet）到一个数组（["aet", "aet", "aet"]）的Map
 */
public class GroupAnagrams {

    public List<List<String>> groupAnagrams(String[] strs) {

        Map<String, List<String>> group = new HashMap<>();
        for(String str : strs){
            String copy = str; //做备份，（key：排序后的字符串；value：原始字符串数组）
            //将字符串里面的字符排序
            char[] chars = copy.toCharArray();
            Arrays.sort(chars);
            StringBuilder sb = new StringBuilder();
            for(char c : chars){
                sb.append(c);
            }
            String sortedStr = sb.toString();
//            System.out.println(sortedStr);
            //分组，存入Map中
            List<String> strList = group.get(sortedStr);
            strList = (strList != null) ? strList : new ArrayList<>();
            strList.add(str);
//            System.out.println(sortedStr + " : " + strList.toString());
            group.put(sortedStr, strList);
        }

        List<List<String>> ans = new ArrayList<List<String>>(); //结果
        Set<String> keySet = group.keySet();
        for(String key : keySet){
            ans.add(group.get(key));
        }

        return ans;
    }


    public static void main(String[] args) {
        //输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
        /*输出: [
                  ["ate","eat","tea"],
                  ["nat","tan"],
                  ["bat"]
                ]*/
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> ans = new GroupAnagrams().groupAnagrams(strs);
        for(List list : ans){
            System.out.println(list.toString());
        }
    }
}
